import java.util.*;

public class OnlyMInPath {
    /**
     * 单源最短路径，利用迪杰斯特拉算法
     */
    class Graph {
        int V;  // 图中顶点的数量
        List<List<Edge>> adjacencyList;  // 邻接表

        // 初始化图
        Graph(int V) {
            this.V = V;
            adjacencyList = new ArrayList<>(V);
            for (int i = 0; i < V; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        // 添加边
        void addEdge(int src, int dest, int weight) {
            Edge edge = new Edge(dest, weight);
            adjacencyList.get(src).add(edge);
        }

        // Dijkstra算法
        int[] dijkstra(int src) {
            PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
            int[] distances = new int[V];
            boolean[] visited = new boolean[V];

            // 初始化距离为无穷大，未访问过
            Arrays.fill(distances, Integer.MAX_VALUE);
            distances[src] = 0;

            minHeap.add(new Node(src, 0));

            while (!minHeap.isEmpty()) {
                int u = minHeap.poll().vertex;
                visited[u] = true;

                for (Edge edge : adjacencyList.get(u)) {
                    int v = edge.dest;
                    int weight = edge.weight;

                    if (!visited[v] && distances[u] + weight < distances[v]) {
                        distances[v] = distances[u] + weight;
                        minHeap.add(new Node(v, distances[v]));
                    }
                }
            }

            return distances;
        }

        class Edge {
            int dest;  // 目标顶点
            int weight;  // 边的权重

            Edge(int dest, int weight) {
                this.dest = dest;
                this.weight = weight;
            }
        }

        class Node {
            int vertex;  // 顶点
            int distance;  // 从源节点到该顶点的距离

            Node(int vertex, int distance) {
                this.vertex = vertex;
                this.distance = distance;
            }
        }
    }

    /**
     * int[] dist = new int[n];  // 存储源节点到每个节点的最短距离
     * boolean[] s = new boolean[n];  // 标记节点是否在S集合中
     * int[] prev = new int[n];  // 存储节点在路径上的前一个节点
     *
     * // 初始化
     * Arrays.fill(dist, Integer.MAX_VALUE);
     * dist[v] = 0;
     * s[v] = true;
     *
     * for (int i = 1; i < n; i++) {  // 遍历n-1次，逐渐扩充S
     *     int temp = Integer.MAX_VALUE;
     *     int u = v;
     *
     *     for (int j = 0; j < n; j++) {  // 找与S距离最近的节点u
     *         if (!s[j] && dist[j] < temp) {
     *             u = j;
     *             temp = dist[j];
     *         }
     *     }
     *
     *     s[u] = true;
     *
     *     for (int j = 0; j < n; j++) {  // 根据新加入S的节点u，更新与不在S中的节点j的距离
     *         if (!s[j] && c[u][j] < Integer.MAX_VALUE) {
     *             int newdist = dist[u] + c[u][j];
     *             if (newdist < dist[j]) {
     *                 dist[j] = newdist;
     *                 prev[j] = u;
     *             }
     *         }
     *     }
     * }
     */
}
